Flash memory is widely used in storage systems because flash memory devices often do not have the mechanical delays associated with hard drives, thereby allowing higher performance in addition to lower cost and less power consumption. A NAND flash memory is usually organized into multiple physical blocks, with each physical block including multiple pages (e.g., 16 pages, 64 pages, 128 pages, etc.). NAND flash memory is often managed using logical blocks that are mapped to the physical blocks, e.g., by a logical-to-physical table. For example, a particular logical block may be mapped to one or more physical blocks.
When new data is to be written to a logical block, the corresponding physical blocks are accessed for the writing operation. Usually, the new data cannot be written to a page if that page has some current data. An erasure operation often needs to be performed on the entire physical block to which the particular page belongs to make that page available for new data.
Oftentimes, a previously used physical block may need to be reclaimed for use (i.e., garbage collection). One or more pages in the physical block may include some old data that is replaced by new data which is stored elsewhere. Such pages are no longer accessible because they are no longer linked with any logical block (e.g., in the logical-to-physical table), and thus the data in these pages becomes invalid. On the other hand, the physical block still has other pages containing valid data and these pages are linked with one or more logical blocks (e.g., referenced by the logical-to-physical table). The garbage collection process may operate by copying the valid data in the physical block to a new physical block and releasing the physical block accordingly, which results in the reclaiming of the entire physical block for storing new data.
FIG. 1 depicts an example diagram for garbage collection. As shown in FIG. 1, valid data in three physical blocks 102, 104 and 106 that are allocated to a logical block 108 are copied to a new physical block 110 for garbage collection. Specifically, the physical blocks 102, 104 and 106 each include valid data and invalid data. The valid data in the physical blocks 102, 104 and 106 is copied to the physical block 110. The physical block 110 is allocated to the logical block 108, and the physical blocks 102, 104 and 106 are released for storing new data.